//
// Created by mac on 2023/11/24.
//

// 串联所有单词的字串
class Solution
{
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        // 1、初始化
        int n = words.size(), step = words[0].size();
        unordered_map<string, int> hash1, hash2;
        for(const auto& e : words) ++hash2[e];
        // 2、滑动窗口
        vector<int> ans;
        for(int i = 0 ; i < step; ++i)
        {
            for(int left = i, right = i, count = 0; right + step <= s.size(); right += step)
            {
                // 进窗口
                string in = s.substr(right, step);
                if(hash2.count(in) && ++hash1[in] <= hash2[in]) ++count;
                // 判断
                while(((right - left) / step + 1) > n)
                {
                    string out = s.substr(left, step);
                    if(hash2.count(out) && hash1[out]-- <= hash2[out]) --count;
                    left += step;
                }
                // 更新结果
                if(count == n) ans.push_back(left);
            }
            // 每完成一组滑动窗口，就重置 hash1
            hash1.clear();
        }
        // 3、返回值
        return ans;
    }
};

// 找到字符串中所有字母异位词
class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        // 1、初始化
        int hash2[26] = {0};
        for(const auto e : p) ++hash2[e - 'a'];
        int hash1[26] = {0};
        int m = 0; // p 字符个数
        for(const auto e : hash2) m += e;
        // 2、滑动窗口
        vector<int> ret;
        for(int left = 0, right = 0, count = 0; right < s.size(); ++right)
        {
            // 进窗口 && 维护 count
            char in = s[right];
            if(++hash1[in - 'a'] <= hash2[in - 'a']) ++count;
            // 出窗口 && 维护 count
            while(right - left + 1 > m)
            {
                char out = s[left++];
                if(hash1[out - 'a']-- <= hash2[out - 'a']) --count;
            }
            // 更新结果 && 维护 count
            if(count == m) ret.push_back(left);
        }
        // 3、返回值
        return ret;
    }
};
/*
- 时间复杂度：O(m + n)
- 空间复杂度：O(1)
*/

// 水果成篮
class Solution
{
public:
    int totalFruit(vector<int>& fruits)
    {
        // 1、初始化
        int ret = 0;
        unordered_map<int, int> hash;
        // 2、滑动窗口
        for(int left = 0, right = 0; right < fruits.size(); ++right)
        {
            // 进窗口
            ++hash[fruits[right]];
            // 判断
            while(hash.size() > 2)
            {
                // 出窗口
                --hash[fruits[left]];
                // 当水果数量为 0 时，把该水果从哈希表中删除
                if(hash[fruits[left]] == 0) hash.erase(fruits[left]);
                // 迭代 left
                ++left;
            }
            // 更新结果
            ret = max(ret, right - left + 1);
        }
        // 3、返回值
        return ret;
    }
};
/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/
